#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include "bstree.h"
#include "rbtree.h"
#include "clock.h"

#define N 300000
#define val 15000

double rate;

void print_indent(long n)
{
  while (n--)
    printf("\t");
}

void print_tree(ptnode p, long baseindent)
{
  print_indent(baseindent);
  printf("(%ld%c\n", p->key, p->color);
  if (p->left != nil)
    print_tree(p->left, baseindent+1);
  else {
    print_indent(baseindent+1);
    printf("Nil,\n");
  }
  if (p->right != nil)
    print_tree(p->right, baseindent+1);
  else {
    print_indent(baseindent+1);
    printf("Nil)\n");
    return;
  }
  print_indent(baseindent);
  printf("),\n");
}

void swap(long *a, long i, long j)
{
  long temp;

  temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

ptnode build_tree(char treetype) /* treetype: 'r':red-black tree; 'b':binary tree */
{
  long i, m[N];
  ptnode t = newtree();
  
  srand((int)time(0));
  for (i = 0; i < N; i++)
    m[i] = i + 1;
  for (i = 0; i < N; i++)
    swap(m, i, (long)(rand() / (RAND_MAX + 1.0) * N));
  if (treetype == 'b')
    for (i = 0; i < N; i++)
      tree_insert(t, newtnode(m[i]));
  if (treetype == 'r')
    for (i = 0; i < N; i++)
      rb_insert(t, newtnode(m[i]));

  return t;
}

double search_time(ptnode t, long x)
{
  start_counter();
  tree_search(treeroot(t), x);

  return get_counter() / rate / 1e6;
}

main()
{
  int i, try_times;
  static double ave_rb ,ave_bs;
  ptnode t;

  printf("------------------------------question (1)------------------------------\n");
  t = newtree();
  ptnode n0 = newtnode(8);
  ptnode n1 = newtnode(11);
  ptnode n2 = newtnode(17);
  ptnode n3 = newtnode(15);
  ptnode n4 = newtnode(6);
  ptnode n5 = newtnode(1);
  ptnode n6 = newtnode(22);
  ptnode n7 = newtnode(25);
  ptnode n8 = newtnode(27);
  rb_insert(t, n0);
  rb_insert(t, n1);
  rb_insert(t, n2);
  rb_insert(t, n3);
  rb_insert(t, n4);
  rb_insert(t, n5);
  rb_insert(t, n6);
  rb_insert(t, n7);
  rb_insert(t, n8);
  print_tree(treeroot(t), 0);
  printf("Blackheight is: %ld\n", blackheight(treeroot(t)));
  printf("---------------------------end of question (1)--------------------------\n\n");

  printf("------------------------------question (2)------------------------------\n");
  rb_delete(t, n3);
  print_tree(treeroot(t), 0);
  printf("Blackheight after deleting the node 15 is: %ld\n", blackheight(treeroot(t)));
  printf("---------------------------end of question (2)--------------------------\n\n");

  printf("------------------------------question (3)------------------------------\n");
  //  printf("Estimating CPU clock rate...\n");
  rate = mhz(1);
  t = build_tree('b');
  printf("Searching time for binary-search tree is: %.10fs\n", search_time(t, val));
  t = build_tree('r');
  printf("Searching time for red-black tree is: %.10fs\n", search_time(t, val));
  printf("---------------------------end of question (3)--------------------------\n\n");

  printf("------------------------------question (4)------------------------------\n");
  i = try_times = 5;
  ave_rb = ave_bs = 0;
  while (i--) {
    t = build_tree('b');
    ave_bs += search_time(t, val) / try_times;
    t = build_tree('r');
    ave_rb += search_time(t, val) / try_times;
  }
  printf("The average searching time for binary-search tree after %d times is: %.10fs\n", try_times, ave_bs);
  printf("The average searching time for red-black tree after %d times is: %.10fs\n", try_times, ave_rb);
  printf("---------------------------end of question (4)--------------------------\n\n");
  printf("------------------------------question (5)------------------------------\n");
  t = newtree();
  rb_insert(t, newtnode(1));
  rb_insert(t, newtnode(2));
  rb_insert(t, newtnode(3));
  rb_insert(t, newtnode(4));
  rb_insert(t, newtnode(5));
  rb_insert(t, newtnode(6));
  rb_insert(t, newtnode(7));
  rb_insert(t, newtnode(8));
  print_tree(treeroot(t), 0);
  printf("The rank of key 6 is: %ld\n", os_key_rank(treeroot(t), 6));
  printf("---------------------------end of question (5)--------------------------\n\n");
  return 0;

}
